package com.demo.sort;

import com.demo.sort.base.SortBase;

/**
 * 快速排序
 * 快速排序其实就是【冒泡排序】的改进.
 * 思路:
 * 1. 选择一个基数, 从两端依次比较,把大于基数的排在右边,小于基数的排在左边.(这一步也就是在确定这个基数在排序后的下标)
 * 2. 再以这个基点为中心,分治成两段.递归处理
 **/
public class QuickSort extends SortBase {

    @Override
    public int[] sort(int[] init) {
        sort(init, 0, init.length - 1);
        return init;
    }

    private void sort(int[] init, int left, int right) {
        if (left >= right) return;
        // 基数下标
        int baseIndex = getBaseIndex(init, left, right);

        // 左排序
        sort(init, left, baseIndex - 1);
        // 右排序
        sort(init, baseIndex + 1, right);
    }

    private int getBaseIndex(int[] init, int left, int right) {
        // 基线
        int baseValue = init[left];
        while (left < right) {
            // 获取右边第一个比基线数小的下标
            while (left < right && init[right] >= baseValue) {
                right--;
            }
            // 放入基线左边
            init[left] = init[right];
            // 获取左边第一个比基线大的下标
            while (left < right && init[left] <= baseValue) {
                left++;
            }
            // 放入基线右边
            init[right] = init[left];
        }
        init[left] = baseValue;
        // 该数在排序后数组中所在下标
        return left;
    }

}
